// Copyright 2023 Google LLC
// Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

#include "modules/bentleyottmann/include/EventQueue.h"
#include "tests/Test.h"

namespace bentleyottmann {
class EventQueueTestingPeer {
public:
    static Event NextEvent(EventQueue *eq)
    {
        SkASSERT(eq->hasMoreEvents());

        auto firstElement = eq->fQueue.begin();

        // Extract event at the beginning of the queue.
        Event event = *firstElement;

        // Remove the beginning element from the queue.
        eq->fQueue.erase(firstElement);

        return event;
    }
};
} // namespace bentleyottmann

using namespace bentleyottmann;

DEF_TEST(BO_EventQueueOrdering, reporter)
{
    { // Check that event types are ordered correctly.
        EventQueue::Queue q;

        // Insert the events in reverse order.
        Point eventPoint = { 100, 100 };
        Segment s = { { 100, 100 }, { 200, 200 } };
        q.insert(Event{ eventPoint, Upper{ s } });
        Segment s0 = { { 50, 50 }, { 150, 150 } }, s1 = { { 150, 50 }, { 50, 150 } };
        q.insert(Event{ eventPoint, Cross{ s0, s1 } });
        q.insert(Event{ eventPoint, Lower{} });

        // Make sure that the events are in the right order.
        auto cursor = q.begin();
        REPORTER_ASSERT(reporter, std::holds_alternative<Lower>(cursor->type));
        ++cursor;
        REPORTER_ASSERT(reporter, std::holds_alternative<Cross>(cursor->type));
        ++cursor;
        REPORTER_ASSERT(reporter, std::holds_alternative<Upper>(cursor->type));
    }
}

DEF_TEST(BO_EventQueueBasic, reporter)
{
    {
        EventQueue::Queue q;
        EventQueue eq{ std::move(q) };
        REPORTER_ASSERT(reporter, !eq.hasMoreEvents());
    }
    {
        EventQueue::Queue q;
        Point eventPoint = { 100, 100 };
        q.insert({ eventPoint, Lower{} });
        EventQueue eq{ std::move(q) };
        {
            REPORTER_ASSERT(reporter, eq.hasMoreEvents());
            Event e = EventQueueTestingPeer::NextEvent(&eq);
            REPORTER_ASSERT(reporter, e.where == eventPoint);
            REPORTER_ASSERT(reporter, !eq.hasMoreEvents());
        }
    }
    { // Check that Lower events are de-duplicated.
        EventQueue::Queue q;
        Point eventPoint = { 100, 100 };
        q.insert({ eventPoint, Lower{} });
        q.insert({ eventPoint, Lower{} });
        EventQueue eq{ std::move(q) };
        {
            // There should be only one lower because of queue de-duplication
            REPORTER_ASSERT(reporter, eq.hasMoreEvents());
            auto [p, _] = EventQueueTestingPeer::NextEvent(&eq);
            REPORTER_ASSERT(reporter, p == eventPoint);
            REPORTER_ASSERT(reporter, !eq.hasMoreEvents());
        }
    }
    { // Check that Lower distinct Lower events are distinct.
        EventQueue::Queue q;
        Point eventPoint1 = { 100, 100 };
        Point eventPoint2 = { 100, 101 };

        q.insert({ eventPoint1, Lower{} });
        q.insert({ eventPoint2, Lower{} });
        EventQueue eq{ std::move(q) };
        {
            // There should be only one lower because of queue de-duplication
            REPORTER_ASSERT(reporter, eq.hasMoreEvents());
            auto [p, _] = EventQueueTestingPeer::NextEvent(&eq);
            REPORTER_ASSERT(reporter, p == eventPoint1);
        }
        {
            // There should be only one lower because of queue de-duplication
            REPORTER_ASSERT(reporter, eq.hasMoreEvents());
            auto [p, _] = EventQueueTestingPeer::NextEvent(&eq);
            REPORTER_ASSERT(reporter, p == eventPoint2);
            REPORTER_ASSERT(reporter, !eq.hasMoreEvents());
        }
    }
    { // Check that non-Lower events are separate.
        EventQueue::Queue q;
        Segment s0{ { 0, 0 }, { 100, 100 } };
        Segment s1{ { 0, 0 }, { -100, 100 } };
        q.insert({ Point{ 0, 0 }, Upper{ s0 } });
        q.insert({ Point{ 0, 0 }, Upper{ s1 } });
        EventQueue eq{ std::move(q) };
        {
            REPORTER_ASSERT(reporter, eq.hasMoreEvents());
            Event e = EventQueueTestingPeer::NextEvent(&eq);
            Point upperPt = Point{ 0, 0 };
            REPORTER_ASSERT(reporter, e.where == upperPt);
            REPORTER_ASSERT(reporter, e.type.index() == 2);
            Upper upper = std::get<Upper>(e.type);
            REPORTER_ASSERT(reporter, !(upper < Upper{ s1 }) && !(Upper{ s1 } < upper));
            Event e2 = EventQueueTestingPeer::NextEvent(&eq);
            REPORTER_ASSERT(reporter, e2.where == upperPt);
            REPORTER_ASSERT(reporter, e2.type.index() == 2);
            Upper upper2 = std::get<Upper>(e2.type);
            REPORTER_ASSERT(reporter, !(upper2 < Upper{ s0 }) && !(Upper{ s0 } < upper2));
            REPORTER_ASSERT(reporter, !eq.hasMoreEvents());
        }
    }
}

enum HasDeletions {
    kHasDeletions,  // The handleDeletions call should be called.
    kHasNoDeletions // The handleDeletions call should not be called.
};

struct TestEventHandler : public SweepLineInterface {
    TestEventHandler(skiatest::Reporter *r, Point eventPoint, SkSpan<const Segment> deletions,
        SkSpan<const Segment> insertions, SkSpan<const Crossing> crossings, HasDeletions hasDeletions = kHasDeletions)
        : fR(r),
          fCandidateEventPoint{ eventPoint },
          fDeletions{ deletions.begin(), deletions.end() },
          fInsertions{ insertions.begin(), insertions.end() },
          fCrossings{ crossings.begin(), crossings.end() },
          fHasDeletions{ hasDeletions }
    {}

    void handleDeletions(Point eventPoint, const DeletionSegmentSet &removing) override
    {
        if (fHasDeletions == kHasNoDeletions) {
            REPORTER_ASSERT(fR, false, "There should be no deletions.");
            return;
        }

        REPORTER_ASSERT(fR, eventPoint == fCandidateEventPoint);

        REPORTER_ASSERT(fR, removing.size() == fDeletions.size());

        for (const Segment &s : fDeletions) {
            REPORTER_ASSERT(fR, removing.find(s) != removing.end());
        }
    }

    void handleInsertionsAndCheckForNewCrossings(Point eventPoint, const InsertionSegmentSet &inserting,
        EventQueueInterface *queue) override
    {
        REPORTER_ASSERT(fR, eventPoint == fCandidateEventPoint);

        REPORTER_ASSERT(fR, inserting.size() == fInsertions.size());

        for (const Segment &s : fInsertions) {
            REPORTER_ASSERT(fR, inserting.find(s) != inserting.end());
        }

        for (const Crossing &crossing : fCrossings) {
            auto [s0, s1, pt] = crossing;
            queue->addCrossing(pt, s0, s1);
        }
    }

    skiatest::Reporter * const fR;
    const Point fCandidateEventPoint;
    std::vector<Segment> fDeletions;
    std::vector<Segment> fInsertions;
    std::vector<Crossing> fCrossings;
    const HasDeletions fHasDeletions;
};

DEF_TEST(BO_EventQueueHandlerInterface, reporter)
{
    { // Check that a Lower event is added while processing the Upper event.
        EventQueue::Queue q;
        static constexpr Point eventPoint = { 100, 100 };
        static constexpr Point endPoint = { 200, 200 };
        static constexpr Segment s = { eventPoint, endPoint };
        q.insert(Event{ eventPoint, Upper{ s } });
        EventQueue eq{ std::move(q) };

        REPORTER_ASSERT(reporter, eq.hasMoreEvents());


        TestEventHandler eh1{ reporter, eventPoint, {}, { s }, {}, kHasNoDeletions };
        eq.handleNextEventPoint(&eh1);

        TestEventHandler eh2{ reporter, endPoint, {}, {}, {} };
        eq.handleNextEventPoint(&eh2);

        REPORTER_ASSERT(reporter, !eq.hasMoreEvents());
    }

    { // Check an entire crossing event.
        EventQueue::Queue q;
        static constexpr Point b0 = { 100, 100 };
        static constexpr Point e0 = { 200, 200 };
        static constexpr Segment s0 = { b0, e0 };
        static constexpr Point b1 = { 200, 100 };
        static constexpr Point e1 = { 100, 200 };
        static constexpr Segment s1 = { b1, e1 };
        static constexpr Point crossingPoint = { 150, 150 };

        // Load crossing segments into the queue
        q.insert(Event{ b0, Upper{ s0 } });
        q.insert(Event{ b1, Upper{ s1 } });
        EventQueue eq{ std::move(q) };

        REPORTER_ASSERT(reporter, eq.hasMoreEvents());

        TestEventHandler eh1{ reporter, b0, {}, { s0 }, {}, kHasNoDeletions };
        eq.handleNextEventPoint(&eh1);

        TestEventHandler eh2{ reporter, b1, {}, { s1 }, { { s0, s1, crossingPoint } }, kHasNoDeletions };
        eq.handleNextEventPoint(&eh2);

        TestEventHandler eh3{ reporter, crossingPoint, { s0, s1 }, { s0, s1 }, {} };
        eq.handleNextEventPoint(&eh3);

        TestEventHandler eh4{ reporter, e1, {}, {}, {} };
        eq.handleNextEventPoint(&eh4);

        TestEventHandler eh5{ reporter, e0, {}, {}, {} };
        eq.handleNextEventPoint(&eh5);

        REPORTER_ASSERT(reporter, !eq.hasMoreEvents());
    }
}
